package com.example.algorithm.dynamicprogramming;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *  求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *  示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 *  示例 2：
 * 输入： heights = [2,4]
 * 输出： 4
 */
public class Leetcode84_LargestRectangleArea {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
//        heights = new int[] {2, 3, 1, 5, 6, 4, 7};
        System.out.println(new Solution().largestRectangleArea(heights));
    }

    static class Solution {
        /**
         * 单调栈进行优化
         * 暴力法求解每个高度对应的宽度时都是分别先前向后进行遍历
         * 优化思路：单调栈
         * 在枚举到第 i 根柱子的时候，就可以先把所有高度大于等于 height[i] 的 j 值全部移除，剩下的 j 值中高度最高的即为答案。
         * 在这之后，将 i 放入数据结构中，开始接下来的枚举
         *
         * @param heights
         * @return
         */
        public int largestRectangleArea2(int[] heights) {
            if (heights == null || heights.length == 0) return 0;
            if (heights.length == 1) return heights[0];

            int len = heights.length;
            int[] left = new int[len];// left[i]表示 heights[i] 的左边界
            int[] right = new int[len];// right[i]表示 heights[i] 的右边界

            Deque<Integer> stack = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i])// 先把所有高度大于等于 height[i] 的值全部移除
                    stack.pollLast();

                left[i] = stack.isEmpty() ? -1 : stack.peekLast();// 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的左边界为 -1(哨兵)
                stack.addLast(i); // i 压入 stack 中，开始下一轮的枚举
            }

            stack.clear(); // 清空栈，为计算所有的右边界做准备

            for (int i = len - 1; i >= 0; i--) {
                while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i])
                    stack.pollLast();
                right[i] = stack.isEmpty() ? len : stack.peekLast();// 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的右边界为 len(哨兵)
                stack.addLast(i);// i 压入 stack 中，开始下一轮的枚举
            }

            // 计算每个高度对应的矩形面积并更新结果
            int res = 0;
            for (int i = 0; i < len; i++) {
                int area = heights[i] * (right[i] - left[i] - 1);
                res = Math.max(res, area);
            }
            return res;
        }

        /**
         * 解法一：暴力法(超时)
         * 枚举所有可能的高，然后求出每个高所对应的宽
         * 遍历每个元素以每个元素为高度 height ，然后分别向前和向后遍历找到该高度下能匹配的最大宽度 width
         *
         * @param heights
         * @return
         */
        public int largestRectangleArea1(int[] heights) {
            if (heights == null || heights.length == 0) return 0;
            if (heights.length == 1) return heights[0];
            int res = 0;

            for (int i = 0; i < heights.length; i++) {
                int height = heights[i];
                int left = i - 1;
                // 从当前元素向前寻找宽的左边界
                while (left >= 0 && heights[left] >= height) {
                    --left;
                }

                // 向后寻找宽的右边界
                int right = i + 1;
                while (right < heights.length && heights[right] >= height) {
                    ++right;
                }
                int width = right - left - 1;

                res = Math.max(res, width * height);

            }
            return res;
        }

        public int largestRectangleArea(int[] heights) {
            return largestRectangleArea2(heights);
        }
    }
}
